package huawei;

import java.util.Map;

/**
 * 狼羊过河
 */
public class Q91 {

    public static void main(String[] args) {
        int M = 5,N =3, X = 3 ; // 羊 狼 小船

        int M1 = 0,N1 =0;

        if (M <= N) {
            System.out.println(0);
            return;
        }

        int dfs = dfs(M, N, M1, N1, X, 0);

        System.out.println(dfs);
    }

    public static int dfs (int M, int N, int M1, int N1, int X, int count) {
        System.out.println("M="+M +" N="+N);
        if (M == 0 && N == 0) {
            System.out.println(count);
            return count;
        }

        int min = Integer.MAX_VALUE;
        for (int i = 0; i <= X; i++) {
            // i 表示每次运羊的数量
            int y = i; // 羊
            int n1 = X - i; // 狼

            for (int n = 0; n <= n1; n++) {
                if (n == 0 && y == 0) continue; // 不要狼和羊都为0的情况

//                M1 += y;
//                N1 += n;

                if (M1 + y != 0 && M1 + y <= N1 + n) {
                    continue;
                }

//                M -= y;
//                N -= n;

                if (M - y < 0 || N - n < 0) {
                    continue;
                }

                if (M - y != 0 && M - y <= N - n) {
                    continue;
                }

                min = Math.min(dfs(M - y, N - n, M1 + y, N1 + n, X, count + 1), min);
            }

        }

        return min;
    }
}
